【week11】456. 132 Pattern 解题报告

456. 132 Pattern

题目

Given a sequence of n integers $a_1, a_2, \dots, a_n$, a 132 pattern is a subsequence $a_i,a_j,a_k$ such that $i<j<k$ and $a_i<a_k<a_j$. Design an algorithm that takes a list of n numbers as input and checks whether there is a 132 pattern in the list.

Note: n will be less than 15,000.

Example 1:

Input: [1, 2, 3, 4]

Output: False

Explanation: There is no 132 pattern in the sequence.

Example 2:

Input: [3, 1, 4, 2]

Output: True

Explanation: There is a 132 pattern in the sequence: [1, 4, 2].

Example 3:

Input: [-1, 3, 2, 0]

Output: True

Explanation: There are three 132 patterns in the sequence: [-1, 3, 2], [-1, 3, 0] and [-1, 2, 0].

解题报告

题意很简单，只要判断数组内存不存在满足 132 范式的子序列即可。

刚开始看见这题还以为必须要子数组，天真的以为很简单。但是做了之后才发现并不容易，题目提示要使用栈，我也往这个方向上靠，尝试了许多种算法，虽然都没过，但是也摸索出了一点准则：假设存在这样的子序列为 s1 < s3 < s2，(s2, s3) 必须尽可能地大，这样 s1 的选择空间才大。

故而，这个问题可以拆成两部分，对于某对 (s2,s3)，查看是否有满足约束的 s1。既然是先找后面的，那不如倒着遍历数组。

现在主要的问题是如何找尽可能大的 (s2,s3)。更准确的说，对于固定的 (s2,s3)，其实只要找到 s1 < s3 即可，不需要理会 s2 是不是尽可能的大。既然如此，我们在遍历数组时，如果当前 nums[i] 不能作为 s1（即 nums[i] > s3 ），则只要判断 nums[i] 能不能和之前的元素构成合法的数对即可（作为 s2 ），并把所有可能合法的数对中最大的 s3 保存下来即可。

虽然主要思路出来了，但是实现还是有点巧妙。实现时把数压进栈中，当出现更大的数（s2）时，就把小于该数的元素弹出，然后再把这个 s2 压入栈中，这样栈将保持正金字塔形，所以刚才最后弹出的必然是所有弹出元素中最大的那个（s3）。

证明：假设 nums[i+1] 作为 s2 时最大的 s3 为 j，则当遍历到 nums[i] 时，栈的内部应为 [...,nums[i+1]]，因为 j 小于 nums[i+1]，所以如果此时 nums[i] > nums[i+1]，则 s3 至少可以更新变大为 nums[i+1]，符合总结出的准则，如果 nums[i] < nums[i+1]，则说明 nums[i] 不能作为 s2，因为不存在小于它的 s3。

Solution

class Solution {
public:
    bool find132pattern(vector<int>& nums) {
        if (nums.empty()) return false;
        stack<int> sk;
        int j = INT_MIN;
        for (int i = nums.size() - 1; i >= 0; --i) {
            if (nums[i] < j) return true;
            while (sk.size() && sk.top() < nums[i]) {
                j = sk.top();
                sk.pop();
            }
            sk.push(nums[i]);
        }
        return false;
    }
};